// the real length in s from p is p[i] - 1
std::vector<int> manacher(std::string s) {
    std::string t = "#";
    for (auto c : s) {
        t += c;
        t += '#';
    }
    int n = t.size();
    std::vector<int> p(n);
    for(int i = 0, r = 0, c = 0, len; i < n; i++) {
        len = r > i ? std::min(p[2 * c - i], r - i) : 1;
        while(i + len < n && i - len >= 0 && t[i + len] == t[i - len]) {
            len++;
        }
        if(i + len > r) {
            r = i + len;
            c = i;
        }
        p[i] = len;
    }
    return p;
}